UVa/11448 - Who said crisis/bigint-2007.07.07/BigUnsignedInABase.hh

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 */
   4
   5 #ifndef BIGUNSIGNEDINABASE
   6 #define BIGUNSIGNEDINABASE
   7
   8 #include "NumberlikeArray.hh"
   9 #include "BigUnsigned.hh"
  10 #include <string>
  11
  12 /*
  13 * A BigUnsignedInABase object represents a nonnegative
  14 * integer of size limited only by available memory,
  15 * represented in a user-specified base that can fit in
  16 * an `unsigned short' (most can, and this saves memory).
  17 *
  18 * BigUnsignedInABase is intended as an intermediary class
  19 * with little functionality of its own.  BigUnsignedInABase
  20 * objects can be constructed from, and converted to,
  21 * BigUnsigneds (requiring multiplication, mods, etc.) and
  22 * `std::string's (by switching digit values for appropriate
  23 * characters).
  24 *
  25 * BigUnsignedInABase is similar to BigUnsigned.  Note the following:
  26 *
  27 * (1) They represent the number in exactly the same way, except
  28 * that BigUnsignedInABase uses ``digits'' (or Digit) where BigUnsigned uses
  29 * ``blocks'' (or Blk).
  30 *
  31 * (2) Both use the management features of NumberlikeArray.  (In fact,
  32 * my desire to add a BigUnsignedInABase class without duplicating a
  33 * lot of code led me to introduce NumberlikeArray.)
  34 *
  35 * (3) The only arithmetic operation supported by BigUnsignedInABase
  36 * is an equality test.  Use BigUnsigned for arithmetic.
  37 */
  38
  39 class BigUnsignedInABase : protected NumberlikeArray<unsigned short> {
  40
  41         // TYPES
  42         public:
  43         typedef unsigned short Digit; // The digit type that BigUnsignedInABases are built from
  44         typedef Digit Base;
  45
  46         // FIELDS
  47         protected:
  48         Base base; // The base of this BigUnsignedInABase
  49
  50         // MANAGEMENT
  51         protected:
  52         // These members generally defer to those in NumberlikeArray, possibly with slight changes.
  53         // It might be nice if one could request that constructors be inherited in C++.
  54
  55         BigUnsignedInABase(int, Index c) : NumberlikeArray<Digit>(0, c) {} // Creates a BigUnsignedInABase with a capacity
  56
  57         void zapLeadingZeros() { // Decreases len to eliminate leading zeros
  58                 while (len > 0 && blk[len - 1] == 0)
  59                         len--;
  60         }
  61
  62         //void allocate(Index c); // (NlA) Ensures the number array has at least the indicated capacity, maybe discarding contents
  63         //void allocateAndCopy(Index c); // (NlA) Ensures the number array has at least the indicated capacity, preserving its contents
  64
  65         public:
  66         BigUnsignedInABase() : NumberlikeArray<Digit>(), base(2) {} // Default constructor (value is 0 in base 2)
  67         BigUnsignedInABase(const BigUnsignedInABase &x) : NumberlikeArray<Digit>(x), base(x.base) {} // Copy constructor
  68
  69         void operator =(const BigUnsignedInABase &x) { // Assignment operator
  70                 NumberlikeArray<Digit>::operator =(x);
  71                 base = x.base;
  72         }
  73
  74         BigUnsignedInABase(const Digit *d, Index l) : NumberlikeArray<Digit>(d, l) { // Constructor from an array of digits
  75                 zapLeadingZeros();
  76         }
  77
  78         // LINKS TO BIGUNSIGNED
  79         BigUnsignedInABase(const BigUnsigned &x, Base base);
  80         operator BigUnsigned() const;
  81
  82         /* LINKS TO STRINGS
  83         *
  84         * These use the symbols ``0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'' to represent
  85         * digits of 0 through 35.  When parsing strings, lowercase is also accepted.
  86         *
  87         * All string representations are big-endian (big-place-value digits first).
  88         * (Computer scientists have adopted zero-based counting; why can't they
  89         * tolerate little-endian numbers?  It makes a lot of sense!)
  90         *
  91         * No string representation has a ``base indicator'' like ``0x''.
  92         *
  93         * An exception is made for zero: it is converted to ``0'' and not the empty string.
  94         *
  95         * If you want different conventions, write your
  96         * own routines to go between BigUnsignedInABase and strings.  It's not hard.
  97         */
  98         operator std::string() const;
  99         BigUnsignedInABase(const std::string &s, Base base);
 100
 101         // PICKING APART
 102         // These accessors can be used to get the pieces of the number
 103         public:
 104         Base getBase() const { return base; }
 105         NumberlikeArray<Digit>::getCapacity; // (NlA)
 106         NumberlikeArray<Digit>::getLength; // (NlA)
 107         // Note that getDigit returns 0 if the digit index is beyond the length of the number.
 108         // A routine that uses this accessor can safely assume a BigUnsigned has 0s infinitely to the left.
 109         Digit getDigit(Index i) const { return i >= len ? 0 : blk[i]; }
 110         // Note how we replace one level of abstraction with another.
 111         bool isZero() const { return NumberlikeArray<Digit>::isEmpty(); } // Often convenient for loops
 112
 113         // EQUALITY TEST
 114         public:
 115         // Equality test
 116         bool operator ==(const BigUnsignedInABase &x) const {
 117                 return base == x.base && NumberlikeArray<Digit>::operator ==(x);
 118         }
 119         bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); }
 120
 121 };
 122
 123 #endif